package leetcode_hot100;

import java.util.*;

public class Demo3 {

    // 146. LRU 缓存
    class LRUCache {
        // 用队列来维护先进先出状态，用 size 来记录有效的缓存个数
        private int capacity;
        private int size = 0;
        private Queue<Integer> q;
        private int[] count;    // 记录在当前缓存中元素出现的次数
        private int[] hash;

        public LRUCache(int capacity) {
            this.capacity = capacity;
            q = new LinkedList<>();
            hash = new int[10001];
            count = new int[10001];
            Arrays.fill(hash, -1);
        }

        public int get(int key) {
            if (count[key] > 0) {   // 存在缓存中，且最近使用过最近使用
                q.offer(key);
                count[key]++;
            }
            return hash[key];
        }

        public void put(int key, int value) {
            // 判断缓存是否溢出，溢出则弹出有效元素
            if (size == capacity && count[key] == 0) {
                while (size == capacity) {
                    Integer front = q.poll();
                    count[front]--;
                    if (count[front] == 0) {
                        size--;
                        hash[front] = -1;
                    }
                }
            }

            q.offer(key);
            hash[key] = value;
            if (++count[key] == 1) size++;
        }
    }



    // 72. 编辑距离
    public int minDistance(String word1, String word2) {
        int n = word1.length(), m = word2.length();
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) dp[i][0] = i;
        for (int i = 1; i <= m; i++) dp[0][i] = i;

        word1 = " " + word1; word2 = " " + word2;
        for (int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                if(word1.charAt(i) == word2.charAt(j)) dp[i][j] = dp[i - 1][j - 1];
                else {
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1]) ) + 1;
                }
            }
        }
        return dp[n][m];
    }



    // 54. 螺旋矩阵
    private List<Integer> res;

    public List<Integer> spiralOrder(int[][] matrix) {
        res = new ArrayList<>();
        int row = matrix.length, col = matrix[0].length;

        for (int i = 0, j = 0; res.size() < row * col; i++, j++) {
            search(matrix, i, j, row - i - 1, col - j - 1);
        }
        return res;
    }

    private void search(int[][] matrix, int x, int y, int row, int col) {
        // 首行搜索
        for (int j = y; j <= col; j++) res.add(matrix[x][j]);
        // 尾列搜索
        for (int i = x + 1; i <= row; i++) res.add(matrix[i][col]);

        if (x == row || y == col) return;

        // 尾行搜索
        for (int j = col - 1; j >= y; j--) res.add(matrix[row][j]);
        // 首列搜索
        for (int i = row - 1; i > x; i--) res.add(matrix[i][y]);
    }



    // 152. 乘积最大子数组
    public int maxProduct(int[] nums) {
        // f[i]: 以 i 位置为结尾的所有子数组中，乘积为正数的最大值
        // g[i]: 以 i 位置为结尾的所有子数组中，乘积为负数的最小值
        int n = nums.length;
        int[] f = new int[n], g = new int[n];
        f[0] = g[0] = nums[0];

        int res = f[0];
        for (int i = 1; i < n; i++) {
            int x = nums[i], y = nums[i] * f[i - 1], z = nums[i] * g[i - 1];
            f[i] = Math.max(x, Math.max(y, z));
            g[i] = Math.min(x, Math.min(y, z));
            res = Math.max(res, f[i]);
        }
        return res;
    }




    // 32. 最长有效括号
    public int longestValidParentheses(String s) {
        // dp[i]: 以 i 为结尾且 s[i]为 ')' 的有效括号子串的最大长度
        int n = s.length();
        if (n < 2) return 0;
        int[] dp = new int[n + 1];
        s = " " + s;

        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') dp[i] = dp[i - 2] + 2;
                else {
                    if (s.charAt(i - dp[i - 1] - 1) == '(') dp[i] = dp[i - 1] + 2 + dp[i - dp[i - 1] - 2];
                }

                res = Math.max(res, dp[i]);
            }
        }
        return res;
    }



    // 48. 旋转图像
    public void rotate(int[][] matrix) {
        int n = matrix.length;
        for (int i = 0; i <= n / 2; i++) {
            for (int j = i; j < n - i - 1; j++) {
                int tmp = matrix[i][j];
                matrix[i][j] = matrix[n - 1 - j][i];                     // 左下->左上
                matrix[n - 1 - j][i] = matrix[n - 1 - i][n - 1 - j];     // 右下->左下
                matrix[n - 1 - i][n - 1 - j] = matrix[j][n - 1 - i];     // 右上->右下
                matrix[j][n - 1 - i] = tmp;                              // tmp->右上
            }
        }
    }


    // 208. 实现 Trie (前缀树)
    class Trie {
        private Trie[] children;
        private boolean isEnd;

        public Trie() {
            children = new Trie[26];
        }

        public void insert(String word) {
            Trie cur = this;
            for (char ch : word.toCharArray()) {
                int index= ch - 'a';
                if (cur.children[index] == null) {
                    cur.children[index] = new Trie();
                }
                cur = cur.children[index];
            }

            cur.isEnd = true;       // 这是一个单词的结束标志
        }

        public boolean search(String word) {
            Trie cur = searchPrefix(word);
            if (cur == null) return false;

            return cur.isEnd;
        }

        public boolean startsWith(String prefix) {
            Trie cur = searchPrefix(prefix);
            if (cur == null) return false;

            for (Trie t : cur.children) {
                if (t != null) return true;
            }
            return cur.isEnd;
        }

        private Trie searchPrefix(String word) {
            Trie cur = this;
            for (char ch : word.toCharArray()) {
                int index= ch - 'a';
                if (cur.children[index] == null) {
                    return null;        // 表示该单词或其前缀不存在
                }
                cur = cur.children[index];
            }
            return cur;
        }
    }



    // 84. 柱状图中最大的矩形
    public static int largestRectangleArea(int[] heights) {
        // 解法：单调栈  思路由来：
        // 1) 暴力解法1：枚举宽度，寻找在宽的区间内柱子的最小高度
        // 2) 暴力解法2：固定高度，从该柱子左右两边寻找高度 >= height[i] 的左右边界(√)
        int n = heights.length;
        Deque<Integer> stack = new LinkedList<>();
        int[] left = new int[n];
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                left[stack.pop()] = i - 1;
            }
            // 先假设后面没有柱子高度小于当前柱子
            left[i] = n - 1;
            stack.push(i);
        }

        stack.clear();
        int[] right = new int[n];
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                right[stack.pop()] = i + 1;
            }
            // // 先假设前面没有柱子高度小于当前柱子
            right[i] = 0;
            stack.push(i);
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res = Math.max((left[i] - right[i] + 1) * heights[i], res);
        }
        return res;
    }




    // 763. 划分字母区间
    public List<Integer> partitionLabels(String s) {
        // 1. 统计每个字符的最远下标
        int[] far = new int[26];
        Arrays.fill(far, -1);
        int n = s.length();
        for (int i = 0; i < n; i++) {
            far[s.charAt(i) - 'a'] = i;
        }

        // 2. 划分区间
        List<Integer> res = new ArrayList<>();
        int right = 0;      // 此次划分区间的右端点
        int prev = -1;      // 上一次划分区间的右端点
        for (int i = 0; i < n; i++) {
            // 更新最远区间
            right = Math.max(right, far[s.charAt(i) - 'a']);
            if (i == right) {
                res.add(right - prev);
                prev = right;
            }
        }
        return res;
    }



    //
    static class LRUCache2 {

        class LinkedNode {
            int key;
            int val;
            LinkedNode prev;
            LinkedNode next;
            public LinkedNode(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }

        Map<Integer,LinkedNode> cache;
        int capacity;
        int size;
        LinkedNode head, tail;

        public LRUCache2(int capacity) {
            this.capacity = capacity;
            cache = new HashMap<>();
        }

        public int get(int key) {
            LinkedNode target = cache.get(key);
            if (target == null) {
                return -1;
            }
            int res = target.val;
            // 当前节点在第一个位置，直接返回结果
            if (target == head) return res;
            // 将该节点移动到链表的第一个节点处
            if (target == tail) {
                removeTail();
            } else {
                removeNode(target);
            }
            addhead(key, res);
            return res;
        }

        public void put(int key, int value) {
            LinkedNode target = cache.get(key);
            if (target != null) {
                if (target == head) removeHead();
                else if (target == tail) removeTail();
                else removeNode(target);
            }
            addhead(key, value);
            if (cache.size() > capacity) {
                removeTail();
            }
        }

        // 删除最近最久未使用
        private void removeTail() {
            cache.remove(tail.key);
            if (head == tail) {
                head = tail = null;
            } else {
                tail = tail.prev;
                tail.next = null;
            }
        }
        // 删除中间节点
        private void removeNode(LinkedNode target) {
            target.prev.next = target.next;
            target.next.prev = target.prev;
            cache.remove(target.key);
            target = null;
        }
        private void removeHead() {
            cache.remove(head.key);
            head = head.next;
        }
        private void addhead(int key, int val) {
            LinkedNode node = new LinkedNode(key, val);
            cache.put(key, node);
            if (head == null) {
                head = tail = node;
                return;
            }
            // 头插法
            node.next = head;
            head.prev = node;
            head = node;
        }
    }


}
